Chưa rõ đền Cuông được lập từ bao giờ, nhưng vào đầu thế kỷ 19, đã thấy Phạm Đình Hổ nói đến trong sách Vũ Trung tùy bút. Các đời vua Nguyễn từ Gia Long đến Khải Định đều cho tu sửa.[1]

Ngay từ thời Đinh, đã thấy dã sử nhắc tới đền Cuông qua sự kiện tướng Võ Trung trấn giữ nơi đây đến thăm đền. Võ Trung là một vị tướng nhà Đinh, có công giúp Đinh Bộ Lĩnh đánh dẹp các sứ quân Ngô Xương Xí, Lã Xử Bình. Khi lên ngôi Hoàng đế, Đinh Tiên Hoàng phong Võ Trung chức đốc trấn châu Hoan. Khi Chiêm Thành sang cướp phá Đại Cồ Việt, ông làm phó tướng cùng Lê Hoàn đem quân đi đánh dẹp và giành thắng lợi.[2]

Khi Lê Hoàn sinh lòng tiếm quốc, lập mưu để Vua Đinh Tiên Hoàng giáng truất Võ Trung làm chức huyện lệnh Đông Thành (Huyện Đông Thành xưa nay là vùng đất thuộc hai huyện Yên Thành và Diễn Châu, tỉnh Nghệ An ngày nay). Võ Trung ở Đông Thành được khoảng một năm, trong huyện yên ổn phong tục dân thuần hậu, được vài năm vua lại vời vào triều cho được khôi phục nguyên chức. Khi Vua Đinh Tiên Hoàng mất, Võ Trung biết ngôi Vua sẽ rơi vào tay Hoàn, ông bèn cáo bệnh lưu nhậm chờ khi nào khỏi bệnh sẽ về. Một hôm ông đến chơi núi Mộ Dạ thuộc huyện Đông Thành vào bái yết đền Cuông, lễ xong khi ấy ông hóa. Đền chính thờ Võ Trung ở nơi qui hóa là núi Mộ Dạ huyện Đông Thành phủ Diễn Châu. Lại một ngôi đền chính nữa là sinh từ ở quê ngoại nay thuộc xã Phạm Ngũ Lão, Kim Động, Hưng Yên. Các triều vua lấy tên huyện do ông trị nhậm thuở trước làm tên ghi sắc phong là Đông Thành đại vương.[3]